package cn.leetcode;

public class Code70 {
    public static void main(String[] args) {
        Code70Demo code70Demo = new Code70Demo();
        int i = code70Demo.climbStairs(3);
        System.out.println(i);
    }
}


class Code70Demo{
    public int climbStairs(int n) {
        return fun(n, new int[n+1]);
    }

    public int fun(int n, int[] arr) {
        if (n == 1 || n == 2) {
            return n;
        }
        if (arr[n] != 0) {
            return arr[n];
        }
        int i = fun(n - 1, arr);
        int j = fun(n - 2, arr);
        arr[n] = i + j;
        return i + j;
    }
}